home *** CD-ROM | disk | FTP | other *** search
/ Internet Publisher's Toolbox 2.0 / Internet Publisher's Toolbox.iso / internet / ntserver / wtsource / irhash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-10  |  13.7 KB  |  401 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4.  
  5.    Brewster@think.com
  6. */
  7.  
  8. /* Copyright (c) CNIDR (see ../COPYRIGHT) */
  9.  
  10.  
  11. /* The memory hashtables for building an index. */
  12. /* -brewster 5/90 */
  13.  
  14. /* Change log:
  15.  * $Log: irhash.c,v $
  16.  * Revision 1.1  1993/02/16  15:05:35  freewais
  17.  * Initial revision
  18.  *
  19.  * Revision 1.16  92/03/20  11:04:33  jonathan
  20.  * Added code to handle switches for word_pairs and word_postition info.
  21.  * 
  22.  * Revision 1.15  92/02/12  13:26:28  jonathan
  23.  * Added "$Log" so RCS will put the log message in the header
  24.  * 
  25. */
  26.  
  27. /* main functions:
  28.  *   add_word
  29.  *   finished_add_word
  30.  *   look_up_word
  31.  *
  32.  * The idea is to store up a bunch of words before going to disk.
  33.  * A word entry points to where it will go on disk, and
  34.  * accumulates the entries before doing it.
  35.  *
  36.  * Some of the policy issues in this file are:
  37.  *   How much weight should the first occurance of a word in a document get
  38.  *   over the other occurances.  The first occurance should be worth more
  39.  *   so that words with 3 occurances of "dog" and not "cat"'s should not 
  40.  *   win out over 1 "dog" and 1 "cat" if the question is "Tell me about cats
  41.  *   torture dogs"
  42.  *   The extra weight is 5 at this point.
  43.  *
  44.  */
  45.  
  46. /* To Do:
  47.  *  done: Improve the hashing functions.
  48.  *  done: stop inserting into hash table after max number have been accumulated
  49.  *  done: make flush not flush buffers that are too big.
  50.  */
  51.  
  52. #include <ctype.h>
  53. #include <string.h>     /* for strlen(), memset() */
  54.  
  55. #include "panic.h"
  56. #include "cutil.h"
  57. #include "irfiles.h"
  58. #include "irhash.h"
  59. #include "stoplist.h"
  60. #include "irinv.h"
  61.  
  62. #ifdef UNIX
  63. #define PRINT_AS_INDEXING true /* also defined in irtfiles.c and irfiles.c */
  64. #else 
  65. #define PRINT_AS_INDEXING false
  66. #endif
  67.  
  68. /* ================================
  69.    ===  Word Occurance Buffers  ===
  70.    ================================ */
  71.  
  72. /* Word occurance buffers
  73.  * This is a simple memory allocator for use with the word memory hashtable.
  74.  * Since the buffers are tiny, this is done as a copy-sweep GC scheme.
  75.  * Oh, I long for the storage system of lisp.
  76.  */
  77. unsigned char *first_word_occurance_buffer = NULL;  /* allocate blocks out of this */
  78. unsigned char *last_word_occurance_buffer = NULL;
  79. long word_occurance_block_length = 256000;  /* maybe this should be larger? */
  80. unsigned char * word_occurance_free_ptr = NULL;
  81.  
  82. unsigned char *make_word_occurrance_block(size)
  83. long size;
  84.  
  85. {
  86.   /* allocates a word_occurance_block out of the buffers */
  87.   /* old way: s_malloc((size_t)size); */
  88.   /* returns a pointer to a piece of memory */
  89.   if(NULL == first_word_occurance_buffer){
  90.     /* initialize it */
  91. #ifdef WIN32
  92.     first_word_occurance_buffer = 
  93.       (unsigned char *)s_malloc(MAX(word_occurance_block_length,
  94.                            (long)sizeof(size_t)+ size));
  95. #else
  96.     first_word_occurance_buffer = 
  97.       (unsigned char *)s_malloc(MAX(word_occurance_block_length,
  98.                            sizeof(size_t)+ size));
  99. #endif
  100.     *(unsigned char **)first_word_occurance_buffer = NULL; /* set the end */
  101.     last_word_occurance_buffer = first_word_occurance_buffer;
  102.     word_occurance_free_ptr = first_word_occurance_buffer + sizeof(size_t);
  103.   }
  104.   if((long)word_occurance_free_ptr + size >= 
  105.      word_occurance_block_length + (long)last_word_occurance_buffer){
  106.     /* then allocate a new block */
  107. #ifdef WIN32
  108.     unsigned char * new_block = (unsigned char *)s_malloc(MAX(word_occurance_block_length,
  109.                                             (long)sizeof(size_t)+ size));
  110. #else
  111.     unsigned char * new_block = (unsigned char *)s_malloc(MAX(word_occurance_block_length,
  112.                                             sizeof(size_t)+ size));
  113. #endif
  114.     *(unsigned char **)new_block = NULL; /* set the end of the chain */
  115.     *(unsigned char **)last_word_occurance_buffer = new_block;
  116.     word_occurance_free_ptr = new_block + sizeof(size_t);
  117.     last_word_occurance_buffer = new_block;
  118.   }
  119.   /* allocate away */   
  120.   { unsigned char * answer = word_occurance_free_ptr;
  121.     word_occurance_free_ptr += size;    
  122.     return(answer);  
  123.   }
  124. }
  125.  
  126. void free_word_occurance_block(block)
  127. unsigned char *block;
  128. {
  129.   /* this is not used with the new scheme, but is here in case
  130.      malloc is a win on some systems */
  131.   /* old way s_free(block); */
  132. }
  133.  
  134. static void flush_word_occur_bufs_internal
  135.   _AP((unsigned char* head_of_list));
  136.  
  137. static void flush_word_occur_bufs_internal(head_of_list)
  138. unsigned char* head_of_list;
  139. /* frees all word occurance buffers.  This should be done with care */
  140. {      
  141.   while(1){
  142.     unsigned char * next_block;
  143.     if(NULL == head_of_list)
  144.       break;
  145.     next_block = *(unsigned char **)head_of_list;
  146.     s_free(head_of_list);
  147.     head_of_list = next_block;
  148.   }
  149. }
  150.  
  151. void flush_word_occurance_buffers()
  152. {
  153.   /* frees all word occurance buffers.  This should be done with care */
  154.   flush_word_occur_bufs_internal(first_word_occurance_buffer);
  155.   first_word_occurance_buffer = NULL;
  156.   word_occurance_free_ptr = NULL;
  157.   last_word_occurance_buffer = NULL;
  158. }
  159.  
  160.  
  161. /* ---------------------------------------------------- */
  162. static hash_entry* look_up_word _AP((char* word,hashtable*
  163.                                      the_word_memory_hashtable));
  164.   
  165. static hash_entry* 
  166. look_up_word(word,the_word_memory_hashtable)
  167. char* word;
  168. hashtable* the_word_memory_hashtable;
  169. {
  170.   hash_entry * answer = get_hash(word, the_word_memory_hashtable);
  171.   
  172.   if(NULL != answer)
  173.     return(answer);
  174.   else{
  175.     hash_entry wrd_entry;
  176.     answer = put_hash(word, the_word_memory_hashtable, &wrd_entry);
  177.     answer->number_of_occurances = 0;
  178.     answer->memory_ptr = 
  179.       make_word_occurrance_block(WORD_MEMORY_INIT_BLOCK_SIZE);
  180.     answer->current_memory_ptr = answer->memory_ptr;
  181.     answer->memory_size = WORD_MEMORY_INIT_BLOCK_SIZE;
  182.     answer->current_doc_id = 0;
  183.     return(answer);
  184.   }
  185. }
  186.  
  187. static unsigned char add_weight _AP((long current_weight,long new_weight));
  188.  
  189. static unsigned char 
  190. add_weight(current_weight,new_weight)
  191. long current_weight;
  192. long new_weight;
  193. /* add a new weight to the existing one */
  194. {
  195.   /* this should be smarter than this, like doing the log or something */
  196.   if(127 < (current_weight + new_weight)){
  197.     /* the max char.  should be 255, but does not work on all compilers */
  198.     return(127);
  199.   }
  200.   else{
  201. #ifdef WIN32
  202.     return ((char)(current_weight + new_weight));
  203. #else
  204.     return(current_weight + new_weight);
  205. #endif
  206.   }
  207. }
  208.  
  209. static unsigned char* more_memory _AP((unsigned char* current_memory_ptr,
  210.                                        long current_memory_size,
  211.                                        long new_size));
  212.  
  213. static unsigned char* more_memory(current_memory_ptr,current_memory_size,new_size)
  214. unsigned char* current_memory_ptr;
  215. long current_memory_size;
  216. long new_size;
  217. /* Allocates more memory for a hash_entry.  It transfers all the bytes 
  218.  * from the old to the new and then returns the new.
  219.  */
  220. {
  221.   unsigned char* new_memory = NULL;
  222.   if(current_memory_size > new_size){
  223.     panic("trying to contract a hash_entry block.  This is not right\n");
  224.   }
  225.   new_memory = make_word_occurrance_block(new_size);
  226.   if(NULL == new_memory){
  227.     panic("Out of memory.");
  228.   }
  229.   memset(new_memory, 0, new_size);
  230.   memmove(new_memory, current_memory_ptr, (size_t)current_memory_size); 
  231.   return(new_memory);
  232. }
  233.  
  234. static long more_memory_size _AP((long current_size,
  235.                                   long number_of_occurances));
  236.  
  237. static long more_memory_size(current_size,number_of_occurances)
  238. long current_size;
  239. long number_of_occurances;
  240. /* This is pretty important to get right.  This is a place holder */
  241. {
  242.   return(MAX(2 * current_size, WORD_MEMORY_INIT_BLOCK_SIZE));
  243. }
  244.  
  245. long write_bytes_to_memory(value,size,ptr)
  246. long value;
  247. long size;
  248. unsigned char* ptr;
  249. {
  250.   /* writes the number into memory lsb first.  
  251.      returns the number of bytes written */
  252.   long i;
  253.   long original_value = value;
  254.  
  255.   if(size < 0) /* paranoia */
  256.     panic("attempting to write a negative number of bytes");
  257.  
  258.   ptr += size; /* start at the end of the block and write backwards */
  259.   for (i = 0; i < size; i++){
  260.     ptr--;
  261.     *ptr = (unsigned char)(value & 0xFF);
  262.     value = value >> 8;
  263.   }
  264.   if(value != 0)
  265.     panic("In a call to write_bytes_to_memory, the value %ld can not be represented in %ld bytes", original_value, size);
  266.  
  267.   return(size);
  268. }
  269.                 
  270. /* adds a word to the hashtable. Returns the 0 if successful. 
  271.    See irext.h for more documentation.
  272.  */
  273. long add_word(word, char_pos, line_pos,
  274.               weight, doc_id, date, word_pair, db, word_position)
  275.      char *word;        /* the word to be indexed, this could be a
  276.                            word pair. If NULL there are no more words
  277.                            to be indexed */
  278.      long char_pos;     /* the position of the start of the
  279.                            word */
  280.      long line_pos;     /* this is passed for the best
  281.                            section calculation */
  282.      long weight;       /* how important the word looks
  283.                            syntactically (such as is it bold)
  284.                            NOT used by signature system */
  285.      long doc_id;       /* current document, this will never be 0 */
  286.      time_t date; /* display day of this document, 0 if not known */
  287.      long word_pair;
  288.      database* db; /* database to insert the document */
  289.      boolean word_position; /* whether to have multiple entries for words in a document */
  290. {
  291.   /* look up the word in the hashtable */
  292.   /* creates it if necessary */ 
  293.   hash_entry* wrd_entry;                                          
  294.   char* newword;
  295.   t_Synonym* syn_Table = db->syn_Table;
  296.   int syn_Table_Size = db->syn_Table_Size;
  297.   hashtable * the_word_memory_hashtable = db->the_word_memory_hashtable;
  298.   /* printf("Word: '%s' doc_id: %ld, pos: %ld, weight: %ld\n",
  299.      word, doc_id, char_pos, weight); */
  300.   
  301.   if(NULL == db->the_word_memory_hashtable){
  302.     panic("The memory word hashtable is not defined.");
  303.   }
  304.  
  305.   /* if we have indexed enough words flush the memory copies to disk. */
  306.   if(db->number_of_words_in_hashtable == db->flush_after_n_words)
  307.     flush_memory_hashtable_to_disk(db, false);
  308.  
  309.   /* perform synonym table lookup and if the word is changed skip WordRoot */
  310.   newword = lookup_Synonym( word,syn_Table,syn_Table_Size );
  311.    strncpy( word,newword,MAX_WORD_LENGTH );
  312.   wrd_entry = look_up_word(word, the_word_memory_hashtable);
  313.   wrd_entry->number_of_occurances ++;
  314.  
  315.   if(wrd_entry->number_of_occurances > MAX_OCCURANCES){
  316.     /* do nothing. we have enough of that word */
  317.   }
  318.   else{
  319.     /* we have a word to add */
  320.     db->number_of_words_in_hashtable ++;
  321.  
  322.     if(word_position || doc_id != wrd_entry->current_doc_id){
  323.       /* then we have a new doc_id to add to the memory block */
  324.           
  325.       /* check to see if we need more memory */
  326.       if((wrd_entry->memory_size -
  327.           (wrd_entry->current_memory_ptr - 
  328.            wrd_entry->memory_ptr) 
  329.           < 
  330.           INDEX_ELEMENT_SIZE)){
  331.         /* we need more memory. this makes more and frees the old*/
  332.         unsigned char* old_memory_ptr = wrd_entry->memory_ptr;
  333.  
  334.         long new_size = 
  335.           more_memory_size(wrd_entry->memory_size,
  336.                            wrd_entry->number_of_occurances);
  337.         /* cprintf(PRINT_AS_INDEXING, "Get more memory %ld bytes for %s\n", new_size, word); */
  338.         wrd_entry->memory_ptr = 
  339.           more_memory(wrd_entry->memory_ptr, wrd_entry->memory_size,
  340.                       new_size);
  341.         wrd_entry->current_memory_ptr = 
  342.           wrd_entry->memory_ptr + /* new offset */
  343.             (wrd_entry->current_memory_ptr - old_memory_ptr);
  344.         /* just being paranoid... no longer illegal
  345.            if(wrd_entry->current_memory_ptr == wrd_entry->memory_ptr)
  346.            panic("After allocating more memory, the size went to 0");
  347.            */
  348.         wrd_entry->memory_size = new_size;
  349.       }                         /* finished making more memory */
  350.  
  351.       /* add away */
  352.       wrd_entry->current_memory_ptr +=
  353.         write_bytes_to_memory(doc_id, DOCUMENT_ID_SIZE,
  354.                               wrd_entry->current_memory_ptr);
  355.       wrd_entry->current_memory_ptr +=
  356.         write_bytes_to_memory(char_pos, 
  357.                               CHARACTER_POSITION_SIZE,
  358.                               wrd_entry->current_memory_ptr);
  359.       wrd_entry->current_memory_ptr +=
  360.         write_bytes_to_memory(weight +
  361.                                /* add 5 since for the first one */
  362.                               (doc_id != wrd_entry->current_doc_id)?5:0,
  363.                               WEIGHT_SIZE,
  364.                               wrd_entry->current_memory_ptr);
  365.       wrd_entry->current_doc_id = doc_id;
  366.  
  367.     }
  368.     else{
  369.       /* The word is already there,
  370.        * just increment the weight in the record.
  371.        * This will change when/if position information is kept (for proximity).
  372.        */
  373.       if(wrd_entry->current_memory_ptr == wrd_entry->memory_ptr){
  374.         panic("Memory hashtable error. Recorded doc_id %ld, current doc_id %ld\n",
  375.               wrd_entry->current_doc_id, doc_id);
  376.       }
  377.       *(wrd_entry->current_memory_ptr - 1) =
  378.         add_weight(*(wrd_entry->current_memory_ptr - 1), weight);
  379.     }
  380.   }
  381.   return(0L);
  382. }
  383.  
  384. void add_stop_words(the_word_memory_hashtable)
  385. hashtable *the_word_memory_hashtable;
  386.      /* add the stop words to the hashtable.  this must be done before
  387.         adding other words */
  388. {
  389.   init_stop_list();
  390.   while(true){
  391.     char *word = next_stop_word();
  392.     hash_entry* wrd_entry;
  393.  
  394.     if(NULL == word)
  395.       break;
  396.     wrd_entry = look_up_word(word, the_word_memory_hashtable);
  397.     wrd_entry->number_of_occurances = STOP_WORD_FLAG;
  398.   }
  399. }
  400.  
  401.